The present invention relates to an N:N+1 channel coding method and apparatus therefor; and, more particularly, to a method and apparatus capable of encoding binary data and decoding transmitted codeword data by using an N:N+1 channel coding algorithm with a higher code rate.
As is well known, demands for optically storing a large amount of data, such as data for a motion picture film, have been increasing. Therefore, various types of volume holographic data storage(VHDS) systems incorporating therein a storage medium have been recently developed for realizing high density optical storage capabilities.
In the VHDS system, source data are segmented into blocks of N data bits, which are also called information bits or message bits, each block capable of representing any of 2N distinct messages. An encoder in the VHDS system transforms each N-bit data block into a larger block of (N+K) bits, called code bits or channel symbols. The K bits, which the encoder adds to each data block, are called redundant bits, parity bits or check bits: they carry no new information. The code is referred to as an (N+K, N) code. The ratio of redundant bits to data bits, K/N, within a block is called redundancy of the code, and the ratio of data bits to total bits, N/(N+K), is called a code rate. The code rate may be thought of as the portion of a code bit that constitutes information. For example, in a rate 1/3 code, each code bit carries 1/3 bit of information. If for example, an error control technique employs a rate 1/3, the redundancy is 2/3 and the bandwidth expansion is only 3.
In other words, the encoder transforms a block of N message digits (a message vector) into a longer block of N+K codeword digits (a code vector), constructed from a given alphabet of elements. When the alphabet consists of two elements (0 and 1), the code is a binary code comprised of binary digits (bits). The explanation provided therein will be confined to binary codes, unless otherwise noted.
The N-bit message forms 2N distinct message sequences referred to as N-tuples (sequences of N digits). The (N+K)-bit blocks can form as many as 2N+K distinct sequences, referred to as (N+K)-tuples. The encoding procedure assigns to each of the 2N message N-tuples one of the 2N+K (N+K)-tuples. A block code represents a one-to-one assignment, whereby the 2N message N-tuples are uniquely mapped into a new set of 2N codeword (N+K)-tuples; and the mapping can be accomplished via a look-up table.
In the decoding mode, a multiplicity of decoding algorithms has been used in order to increase the code rate while decreasing the bit error rate.
In a threshold decoding algorithm, a threshold, e.g., an average value or a predetermined value such as 0.5, may be used to assign xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99 to a retrieved or transmitted signal disturbed by channel distortion. In the conventional VHDS system, Gaussian distribution characteristics of a laser beam, lens distortions, scattering and diffraction in the system and so on may be appreciated as a channel. The threshold decoding algorithm has a higher code rate, but also has a higher bit error rate, specifically, with a lower intensity of laser beam.
An improvement may be realized by using a local threshold decoding algorithm. The local threshold decoding algorithm divides a decoding region into a plurality of local regions and applies a different threshold for each local region so as to determine xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99. The local threshold decoding algorithm has a low compatibility because each of the VHDS systems has intrinsic noise patterns different from each other.
Another improvement may be realized by using a binary differential decoding algorithm. The binary differential decoding algorithm uses a characteristic that a signal for representing xe2x80x981xe2x80x99 is always larger than a signal for representing its nearest xe2x80x980xe2x80x99. For example, xe2x80x980xe2x80x99 and xe2x80x981xe2x80x99 are replaced with xe2x80x9801xe2x80x99 and xe2x80x9810xe2x80x99, respectively, to be encoded and its reverse algorithm is used to decode a transmitted signal. The binary differential decoding algorithm has a lower bit error rate, but its code rate is also comparatively decreased.
Another improvement may be achieved by employing a balanced block decoding algorithm. The balanced block decoding algorithm divides an input message into a plurality of message P-tuples and each message P-tuple is encoded with a codeword 2Q-tuple, wherein the number of lower bits is equal to that of higher bits, 2Q being larger than P. In a decoding mode, a transmitted signal is divided into a plurality of codeword 2Q-tuples; and Q number of lower and higher bits for each codeword 2Q-tuple are reconstructed as xe2x80x980xe2x80x99 and xe2x80x981xe2x80x99, respectively. For example, in a 6:8 balanced block decoding algorithm only 26(=64) codeword 8-tuples which have the same number, i.e., 4 of lower and higher bits among 28(=256) codeword 8-tuples are selected to encode 64 message 6-tuples. The balanced block coding algorithm has a lower bit error rate and a higher code rate than the binary differential coding algorithm; however, a still higher code rate is required to use a limited channel resource effectively.
It is, therefore, an object of the present invention to provide a method and apparatus capable of encoding binary data and decoding transmitted codeword data by using an N:N+1 channel coding algorithm with a much increased code rate with a reduced bit error rate.
In accordance with a preferred embodiment of the present invention, there is provided a method for mapping 2N message N-tuples into 2N+1 codeword (N+1)-tuples, wherein said each of N-tuples and (N+1)-tuples is a binary code comprised of bits, 0 and 1, comprising the steps of:
(a) categorizing the 2N+1 codeword (N+1)-tuples into M subsets of codeword (N+1)-tuples, wherein M is an integer larger than 1, each subset G has NG codeword (N+1)-tuples, NG being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2N given as follows:                     ∑                  G          =          1                M            ⁢              N        G              =          2      N        ,
xe2x80x83is wherein the each subset G has a predetermined number KG of lower bits and a predetermined number (N+1xe2x88x92KG) of higher bits and the number of lower bits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower bits in every codeword (N+1)-tuple in any other subset; and
(b) matching the 2N message N-tuples with the 2N codeword (N+1)-tuples in the M subsets, respectively, in one-to-one correspondence to generate a lookup table.